package leetcode

type Heap struct {
	Max bool
	values []int
}

// down := i*2+1
// parent := (i-1)/2

func InitHeap(arr []int) *Heap {
	h := &Heap{
		Max:    false,
		values: arr,
	}
	return h
}

func (h *Heap) init() {
	n := len(h.values)
	for t := n/2 - 1; t >= 0; t-- {
		i := t
		for {
			llp := i*2 + 1
			lrp := i*2 + 2
			if llp >= n {
				break
			}

			if h.Max {
				if lrp >= n {
					if h.values[llp] < h.values[i] {
						h.Swap(llp, i)
					}
					i = llp
					break
				}
				if h.values[llp] < h.values[lrp] && h.values[llp] < h.values[i] {
					h.Swap(llp, i)
					i = llp
				} else if h.values[lrp] < h.values[i] {
					h.Swap(lrp, i)
					i = lrp
				}
			}else {
				if lrp >= n {
					if h.values[llp] > h.values[i] {
						h.Swap(llp, i)
					}
					i = llp
					break
				}
				if h.values[llp] > h.values[lrp] && h.values[llp] > h.values[i] {
					h.Swap(llp, i)
					i = llp
				} else if h.values[lrp] > h.values[i] {
					h.Swap(lrp, i)
					i = lrp
				}
			}
		}
	}
}

func (h *Heap) up(pos int) {
	i := (pos - 1) / 2 // parent
	for {
		if i == pos || !h.Less(pos, i) {
			break
		}
		h.Swap(i, pos)
		pos = i
	}
}

func (h *Heap) down(pos, n int) bool {
	i := pos
	for {
		jl := 2*i + 1
		if jl >= n || jl < 0 { // jl < 0 after int overflow
			break //下级元素超出了，证明是叶子节点,不需要down
		}
		j := jl // left child
		if jr := jl + 1; jr < n && h.Less(jr, jl) {
			j = jr // = 2*i + 2  // right child
		}
		if !h.Less(j, i) {
			break
		}
		h.Swap(i, j)
		i = j
	}
	return i > pos
}

// Less 比较
func (h *Heap) Less(i, j int) bool {
	if h.Max {
		return h.values[i] > h.values[j]
	}
	return h.values[i] < h.values[j]
}

// Swap 比较
func (h *Heap) Swap(i, j int) {
	h.values[i], h.values[j] = h.values[j], h.values[i]
}
